﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 编译原理
{
    public static class 实验三
    {
        #region 变量
        class Production
        {
            public Production()
            {
                Rights = new List<string>();
                First = new List<char>();
                Last = new List<char>();
                Visit = new List<char>();
                Projects = new List<List<string>>();
            }
            public char left { get; set; }
            public List<string> Rights { get; set; }
            public List<char> First { get; set; }
            public List<char> Last { get; set; }
            public List<char> Visit { get; set; }
            public List<List<string>> Projects { get; set; }
        }
        //产生式
        private static List<Production> productions { get; set; } = new List<Production>();
        //拓广文法
        private static Dictionary<KeyValuePair<char, string>, int> Broaden = new Dictionary<KeyValuePair<char, string>, int>();
        //算符优先关系表
        //private static List<List<char>> PrecedenceTable { get; set; } = new List<List<char>>();
        //终结符字典 下标映射 
        private static Dictionary<char, int> Terminator { get; set; } = new Dictionary<char, int>();
        //非终结符集合
        private static List<char> NonTerminator { get; set; } = new List<char>() { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
        //分析栈
        private static string mStack { get; set; } = "";
        //待分析字符串队列
        private static string mQueue { get; set; } = "";
        //当前状态
        private static List<int> mState { get; set; } = new List<int>();
        //项目集规范族
        private static List<List<Family>> CanonicalFamily { get; set; } = new List<List<Family>>();
        //活前缀DFA
        private static List<List<KeyValuePair<char, int>>> DFA { get; set; } = new List<List<KeyValuePair<char, int>>>();
        //FIRST集
        private static Dictionary<string, HashSet<char>> FirstSet = new Dictionary<string, HashSet<char>>();
        //FOLLOW集
        private static Dictionary<string, HashSet<char>> FollowSet = new Dictionary<string, HashSet<char>>();
        //ACTION表GOTO表
        private static List<List<string>> ActionGoto { get; set; } = new List<List<string>>();
        //ACTION表的映射关系
        private static Dictionary<char, int> ActionMap = new Dictionary<char, int>
        {
            { ' ', 0 },
            { '+', 1 },
            { '*', 2 },
            { '(', 3 },
            { ')', 4 },
            { 'i', 5 },
            { '#', 6 },
        };
        //Goto表的映射关系
        private static Dictionary<char, int> GotoMap = new Dictionary<char, int>
        {
            { 'E', 7 },
            { 'T', 8 },
            { 'F', 9 },
        };
        //消除左递归用的产生式
        private static Dictionary<string, List<string>> grammar { get; set; } = new Dictionary<string, List<string>>
        {
            { "E", new List<string> { "E+T", "T" } },
            { "T", new List<string> { "T*F", "F" } },
            { "F", new List<string> { "(E)", "i" } }
        };


        //规范族
        class Family
        {
            public Family(int a, int b, int c)
            {
                A = a;
                B = b;
                C = c;
            }
            public int A { get; set; }
            public int B { get; set; }
            public int C { get; set; }
            public bool Equals(Family other)
            {
                return other.A == A && other.B == B && other.C == C;
            }
        }
        #endregion
        public static void LR分析()
        {
            ReadFile();
            GrammarProject();
            CreatCanonicalFamily();
            ShowDFA();
            LeftRecursionEliminator();
            CalculateFirstSets();
            CalculateFollowSets();
            CreatActionGotoTable();
            Analyse();
        }
        #region 读取文法
        static void ReadFile()
        {
            try
            {
                using (StreamReader sr = new StreamReader("../../file1.txt"))
                {
                    string line;
                    char[] chars = { ' ', '|', '#' };
                    while ((line = sr.ReadLine()) != null)
                    {
                        //Console.WriteLine(line);
                        var tempLine = line.Split(chars, StringSplitOptions.RemoveEmptyEntries);
                        var tempProduction = new Production();
                        tempProduction.left = tempLine[0][0];
                        for (int i = 2; i < tempLine.Length; i++)
                        {
                            tempProduction.Rights.Add(tempLine[i]);
                        }
                        productions.Add(tempProduction);
                    }
                }
            }
            catch (Exception e)
            {
                Console.WriteLine("The file could not be read:");
                Console.WriteLine(e.Message);
            }
            //输出
            Console.WriteLine($"-----扩展文法-----------------");
            int cnt = 0;
            foreach (var item in productions)
            {
                foreach (var item2 in item.Rights)
                {
                    Console.WriteLine($"{item.left} -> {item2}");
                    Broaden.Add(new KeyValuePair<char, string>(item.left, item2), cnt++);
                }
            }
            Console.WriteLine();
        }
        #endregion
        #region 文法项目
        static void GrammarProject()
        {
            foreach (var production in productions)
            {
                for (int i = 0; i < production.Rights.Count; i++)
                {
                    var right = production.Rights[i];
                    production.Projects.Add(new List<string>());
                    var project = production.Projects[i];
                    for (int j = 0; j <= right.Length; j++)
                    {
                        project.Add(right.Insert(j, "."));
                    }
                }
            }

            Console.WriteLine($"-----文法的项目:--------------");
            foreach (var production in productions)
            {
                Console.Write($" {production.left} : ");
                foreach (var project in production.Projects)
                {
                    foreach (var item in project)
                    {
                        Console.Write($" {item} ");
                    }
                }
                Console.WriteLine();
            }
        }
        #endregion
        #region 项目集规范族
        static void CreatCanonicalFamily()
        {
            CanonicalFamily.Add(new List<Family>());
            CanonicalFamily[0].Add(new Family(0, 0, 0));
            for (int k = 0; k < CanonicalFamily.Count; k++)
            {
                var family = CanonicalFamily[k];
                //活前缀DFA
                DFA.Add(new List<KeyValuePair<char, int>>());
                //扩展当前行
                ExCurrentLine(family);
                //扩展其他状态
                List<char> newLines = new List<char>();
                //当前状态的所有下一个输入
                foreach (var f in family)
                {
                    var production = productions[f.A];
                    if (f.C == production.Rights[f.B].Length) continue;
                    char next = production.Rights[f.B][f.C];
                    if (!newLines.Contains(next)) newLines.Add(next);
                }
                //遍历每种输入产生的状态
                foreach (var line in newLines)
                {
                    var tempLine = new List<Family>();
                    foreach (var f in family)
                    {
                        var production = productions[f.A];
                        if (f.C == production.Rights[f.B].Length) continue;
                        char next = production.Rights[f.B][f.C];
                        if (line == next)
                        {
                            tempLine.Add(new Family(f.A, f.B, f.C + 1));
                        }
                    }
                    ExCurrentLine(tempLine);
                    int idx = IdxofLine(tempLine);
                    if (idx == -1)
                    {
                        //记录状态转移
                        DFA[k].Add(new KeyValuePair<char, int>(line, CanonicalFamily.Count));
                        //添加新规范族
                        CanonicalFamily.Add(tempLine);
                    }
                    else
                    {
                        DFA[k].Add(new KeyValuePair<char, int>(line, idx));
                    }
                }
            }
            Console.WriteLine($"-----项目集规范族:------------");
            for (int i = 0; i < CanonicalFamily.Count; i++)
            {
                Console.Write($" I{i} :");
                var family = CanonicalFamily[i];
                foreach (var f in family)
                {
                    Console.Write($" {productions[f.A].left}->{productions[f.A].Projects[f.B][f.C]}   ");
                }
                Console.WriteLine();
            }

        }
        //扩展当前行
        static void ExCurrentLine(List<Family> family)
        {
            for (int i = 0; i < family.Count; i++)
            {
                var f = family[i];
                var production = productions[f.A];
                // .在最后
                if (f.C == production.Rights[f.B].Length) continue;
                //下一个字符
                char next = production.Rights[f.B][f.C];
                if (NonTerminator.Contains(next))
                {
                    //非终结符不在当前规范族中
                    if (family.Where(fa => productions[fa.A].left == next && fa.C == 0).Count() == 0)
                    {
                        //找下标
                        int a = productions.IndexOf(productions.Where(p => p.left == next).First());
                        for (int b = 0; b < productions[a].Projects.Count; b++)
                        {
                            family.Add(new Family(a, b, 0));
                        }
                    }
                }
            }
        }
        static int IdxofLine(List<Family> family)
        {
            for (int i = 0; i < CanonicalFamily.Count; i++)
            {
                var fam = CanonicalFamily[i];
                bool equal = true;
                for (int j = 0; j < family.Count; j++)
                {
                    if (!family[j].Equals(fam[j]))
                    {
                        equal = false;
                        break;
                    }
                }
                if (equal)
                    return i;
            }
            return -1;
        }
        #endregion
        #region 识别活前缀的DFA
        static void ShowDFA()
        {
            Console.WriteLine($"-----识别活前缀的DFA:---------");
            for (int i = 0; i < DFA.Count; i++)
            {
                foreach (var q in DFA[i])
                {
                    Console.WriteLine($" (I{i},{q.Key})=I{q.Value}");
                }
            }
        }
        #endregion
        #region 消除左递归
        static void LeftRecursionEliminator()
        {
            grammar = EliminateLeftRecursion(grammar);
            Console.WriteLine($"-----消除左递归:--------------");
            foreach (var nonTerminal in grammar.Keys)
            {
                Console.WriteLine($"{nonTerminal} -> {string.Join(" | ", grammar[nonTerminal])}");
            }
        }
        //消除左递归
        static Dictionary<string, List<string>> EliminateLeftRecursion(Dictionary<string, List<string>> grammar)
        {
            var newGrammar = new Dictionary<string, List<string>>();

            foreach (var nonTerminal in grammar.Keys)
            {
                var list1 = new List<string>();
                var list2 = new List<string>();

                foreach (var production in grammar[nonTerminal])
                {
                    if (production.StartsWith(nonTerminal))
                    {
                        list1.Add(production.Substring(nonTerminal.Length));
                    }
                    else
                    {
                        list2.Add(production);
                    }
                }

                if (list1.Count > 0) 
                {
                    var newNonTerminal = $"{nonTerminal}'";   
                    newGrammar[nonTerminal] = list2.Select(b => $"{b}{newNonTerminal}").ToList();
                    newGrammar[newNonTerminal] = list1.Select(a => $"{a}{newNonTerminal}").ToList();
                    newGrammar[newNonTerminal].Add("ε");
                }
                else
                {
                    newGrammar[nonTerminal] = grammar[nonTerminal];
                }
            }

            return newGrammar;
        }
        #endregion
        #region First集
        //First集
        static void CalculateFirstSets()
        {
            bool changed;

            // Initialize FIRST sets
            foreach (var nonTerminal in grammar.Keys)
            {
                FirstSet[nonTerminal] = new HashSet<char>();
            }

            do
            {
                changed = false;

                foreach (var nonTerminal in grammar.Keys)
                {
                    foreach (var production in grammar[nonTerminal])
                    {
                        var firstSymbol = production[0];

                        // If the first symbol is a terminal, add it
                        if (!grammar.ContainsKey(firstSymbol.ToString()))
                        {
                            if (!FirstSet[nonTerminal].Contains(firstSymbol))
                            {
                                changed = true;
                                FirstSet[nonTerminal].Add(firstSymbol);
                            }
                        }
                        // Otherwise, add the first set of the non-terminal
                        else
                        {
                            var countBefore = FirstSet[nonTerminal].Count;
                            FirstSet[nonTerminal].UnionWith(FirstSet[firstSymbol.ToString()]);
                            if (countBefore != FirstSet[nonTerminal].Count) changed = true;
                        }
                    }
                }
            } while (changed);

            Console.WriteLine($"-----FIRST集:-----------------");
            foreach (var nonTerminal in FirstSet.Keys)
            {
                Console.WriteLine($"{nonTerminal}: {string.Join(" ", FirstSet[nonTerminal])}");
            }
        }
        #endregion
        #region Follow集
        //Follow集
        static void CalculateFollowSets()
        {
            FollowSet = new Dictionary<string, HashSet<char>>()
            {
                { "E",new HashSet<char>{')','#' } },
                { "E'",new HashSet<char>{')','#' } },
                { "T",new HashSet<char>{'+',')','#' } },
                { "T'",new HashSet<char>{'+',')','#' } },
                { "F",new HashSet<char>{'+','*',')','#'} },
            };
            Console.WriteLine($"-----FOLLOW集:----------------");
            foreach (var nonTerminal in FollowSet.Keys)
            {
                Console.WriteLine($"{nonTerminal}: {string.Join(" ", FollowSet[nonTerminal])}");
            }
        }
        #endregion
        #region LR分析表
        static void CreatActionGotoTable()
        {
            //初始化
            for (int i = 0; i < CanonicalFamily.Count; i++)
            {
                ActionGoto.Add(new List<string>());
                ActionGoto[i].Add($"I{i}");
                for (int j = 1; j < 10; j++)
                {
                    ActionGoto[i].Add("-");
                }
            }
            //记录移进ACTION
            for (int i = 0; i < DFA.Count; i++)
            {
                foreach (var q in DFA[i])
                {
                    if (ActionMap.ContainsKey(q.Key))
                    {
                        ActionGoto[i][ActionMap[q.Key]] = $"S{q.Value}";
                    }
                    else if (GotoMap.ContainsKey(q.Key))
                    {
                        ActionGoto[i][GotoMap[q.Key]] = q.Value.ToString();
                    }
                }
            }
            //记录归约ACTION
            for (int k = 0; k < CanonicalFamily.Count; k++)
            {
                var family = CanonicalFamily[k];
                foreach (var f in family)
                {
                    var production = productions[f.A];
                    if (f.C == production.Rights[f.B].Length)
                    {
                        char c = production.Rights[f.B][f.C - 1];
                        int r = Broaden[new KeyValuePair<char, string>(production.left, production.Rights[f.B])];
                        if (r == 0)
                        {
                            ActionGoto[k][ActionMap['#']] = "acc";
                            continue;
                        }
                        if (ActionMap.ContainsKey(c))
                        {
                            foreach (var v in FollowSet[production.left.ToString()])
                            {
                                ActionGoto[k][ActionMap[v]] = $"R{r}";
                            }

                        }
                        else if (GotoMap.ContainsKey(c))
                        {
                            foreach (var v in FollowSet[c.ToString()])
                            {
                                ActionGoto[k][ActionMap[v]] = $"R{r}";
                            }
                        }
                    }

                }
            }

            Console.WriteLine($"-----LR分析表:----------------");
            Console.WriteLine($"状态    ACTION                                          GOTO");
            foreach (var ch in ActionMap)
                Console.Write($"{ch.Key}\t");
            foreach (var ch in GotoMap)
                Console.Write($"{ch.Key}\t");
            Console.WriteLine();
            for (int i = 0; i < ActionGoto.Count; i++)
            {
                foreach (var s in ActionGoto[i])
                {
                    Console.Write($"{s}\t");
                }
                Console.WriteLine();
            }
        }
        #endregion
        #region 分析句子
        //分析初始化
        static void Analyse()
        {
            Console.WriteLine($"-----分析句子-----------------");
            //待分析句子
            List<string> list = new List<string>()
            {
                "(i+i)*i#",
                "i+i)*i#",
            };
            foreach (var item in list)
            {
                Console.WriteLine($"--- {item} ---");
                if (AnalyseProcess(item))
                {
                    Console.WriteLine("识别成功");
                }
                else
                {
                    Console.WriteLine("识别失败");
                }
                Console.WriteLine();
            }
        }
        //分析过程
        static bool AnalyseProcess(string s)
        {
            mStack = "#";
            mQueue = s;
            mState.Add(0);

            while (mQueue.Length > 0)
            {
                var c = mQueue.First();
                int state = mState.Last();
                var action = ActionGoto[state][ActionMap[c]];

                if (action == "acc")
                {
                    Console.WriteLine($"{string.Join("", mState)}\t\t{mStack}\t\t{mQueue}\t\t接受");
                    return true;
                }
                else if(action == "-")
                {
                    return false;
                }
                //移进
                else if (action.StartsWith("S"))
                {
                    IntoTheStack(action);
                }
                //归约
                else if (action.StartsWith("R"))
                {
                    if (!Reduce(action)) { return false; }
                }
            }
            return false;
        }
        //进栈
        static void IntoTheStack(string action)
        {
            mStack += mQueue[0];
            mQueue = mQueue.Remove(0, 1);
            mState.Add(Convert.ToInt32(action.Substring(1)));
            Console.WriteLine($"{string.Join("", mState)}\t\t{mStack}\t\t{mQueue}\t\t进栈");
        }
        //归约
        static bool Reduce(string action)
        {
            int t = Convert.ToInt32(action.Substring(1));
            var reduce = Broaden.Where(o => o.Value == t).Select(o => o.Key).FirstOrDefault();
            mState.RemoveRange(mState.Count - reduce.Value.Length, reduce.Value.Length);
            int state = mState.Last();
            int x = Convert.ToInt32(ActionGoto[state][GotoMap[reduce.Key]]);
            mState.Add(x);
            mStack = mStack.Remove(mStack.Length - reduce.Value.Length);
            mStack += reduce.Key;
            Console.WriteLine($"{string.Join("", mState)}\t\t{mStack}\t\t{mQueue}\t\t归约");
            return true;
        }
        #endregion
    }
}
